{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "    def __str__(self):\n",
    "        return self.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Single_link_node:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.pre = None\n",
    "        self.next = None\n",
    "    def __str__(self):\n",
    "        return self.head\n",
    "    def is_empty(self):\n",
    "        if self:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "    def get_head(self):\n",
    "        x = self\n",
    "        while x.pre!=None:\n",
    "            x = x.pre\n",
    "        x = x.next\n",
    "        print(x.head.val)\n",
    "        return x\n",
    "    def get_tail(self):\n",
    "        x = self\n",
    "        while x.next!=None:\n",
    "            x = x.next\n",
    "        return x\n",
    "    def search(self,key):\n",
    "        '''\n",
    "         @brief:  search for the first head whose value is equal to the \"key\". If it is no any node that conform to the demand\n",
    "         @param:  self: Single_link_node ; val: the item needed to search\n",
    "         @return: x:a Single_link_node\n",
    "        '''\n",
    "        x = self.head\n",
    "        while x and (x.val!=key):\n",
    "            x = x.next\n",
    "        return x\n",
    "    def search_all(self, key):\n",
    "        '''\n",
    "         @brief:  search for all head(s) whose value isqual to \"val\", and it won't stop when find a head.\n",
    "         @param:  self: Single_link_node ; val: the item needed to search\n",
    "         @return: aim_link_node: Single_link_node\n",
    "        '''\n",
    "        x = self.head        # point of self\n",
    "        aim_link_node = None  \n",
    "        x_2 = aim_link_node  # point of aim\n",
    "        while x:\n",
    "            if(x.val==key):\n",
    "                x_2 = x\n",
    "                x_2.next = None\n",
    "            x_2 = x_2.next\n",
    "        return aim_link_node\n",
    "    def insert_pre(self, x):\n",
    "        # finish insert\n",
    "        x.pre = self.pre\n",
    "        self.pre = x\n",
    "        # complete point of node\n",
    "        x.next = self\n",
    "        x.pre.next = x\n",
    "    def insert_post(self, x):\n",
    "        # finish insert\n",
    "        x.next = self.next\n",
    "        self.next = x\n",
    "        # complete point of node\n",
    "        x.pre = self\n",
    "        x.next.pre = x\n",
    "    \n",
    "    def delete(self):\n",
    "        '''\n",
    "        delete the node(self),but won't set self.pre or self.next to None\n",
    "        '''\n",
    "        self.pre.next = self.next\n",
    "        self.next.pre = self.pre\n",
    "        return self.pre\n",
    "    \n",
    "    def delete_completed(self):\n",
    "        '''\n",
    "        delete the node(self), then, set self.pre and self.next to None\n",
    "        '''\n",
    "        self.pre.next = self.next\n",
    "        self.next.pre = self.pre\n",
    "        #-------------------------------------------------\n",
    "        new_point = self.pre\n",
    "        self.pre = None\n",
    "        self.next = None\n",
    "        self = None\n",
    "    def show(self):\n",
    "        while self != None:\n",
    "            print(self.head.val)\n",
    "            self = self.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_1 = Node(1)\n",
    "node_2 = Node(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "single_link_node_1 = Single_link_node()\n",
    "single_link_node_2 = Single_link_node()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "single_link_node_1.node = node_1\n",
    "single_link_node_2.node = node_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "single_link_node_1_head = Single_link_node()\n",
    "single_link_node_1_head = node_1\n",
    "\n",
    "single_link_node_2_head = Single_link_node()\n",
    "single_link_node_2_head = node_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'val'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-57-da9742fdf0f3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mSingle_link_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msingle_link_node_1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-51-2f44578747af>\u001b[0m in \u001b[0;36mshow\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     84\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     85\u001b[0m         \u001b[0;32mwhile\u001b[0m \u001b[0mself\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 86\u001b[0;31m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhead\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     87\u001b[0m             \u001b[0mself\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'val'"
     ]
    }
   ],
   "source": [
    "Single_link_node.show(single_link_node_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "single_link_node_1.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s\n",
      "s\n",
      "a\n",
      "1\n",
      "\n",
      "#\n"
     ]
    }
   ],
   "source": [
    "val = 0\n",
    "while True:\n",
    "    val = input()\n",
    "    if val != '#':\n",
    "        node = Node(0)\n",
    "        node.val = val\n",
    "        Single_link_node.insert_post(single_link_node_1,node)\n",
    "    else:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'Node' object has no attribute 'head'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-43-095a753da8f4>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mSingle_link_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_head\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msingle_link_node_1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-42-4bebdfa15c8d>\u001b[0m in \u001b[0;36mget_head\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     16\u001b[0m             \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpre\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m         \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhead\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     19\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mget_tail\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'Node' object has no attribute 'head'"
     ]
    }
   ],
   "source": [
    "Single_link_node.get_head(single_link_node_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "get_head() got multiple values for argument 'self'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-37-22a806d1658b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mSingle_link_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msingle_link_node_1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-36-bc99315c4627>\u001b[0m in \u001b[0;36mshow\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     81\u001b[0m         \u001b[0mself\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     82\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 83\u001b[0;31m         \u001b[0mhead\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_head\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     84\u001b[0m         \u001b[0;32mwhile\u001b[0m \u001b[0mhead\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     85\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhead\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: get_head() got multiple values for argument 'self'"
     ]
    }
   ],
   "source": [
    "Single_link_node.show(self=single_link_node_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_head = Single_link_node.get_head(single_link_node_1)\n",
    "x_2 = node_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_head.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'val'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-19-9dcba760308d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mx_2\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx_2\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhead\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m     \u001b[0mx_2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mx_2\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'val'"
     ]
    }
   ],
   "source": [
    "while x_2!=None:\n",
    "    print(x_2.head.val)\n",
    "    x_2 = x_2.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "single_link_node_1.node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Single_link_node.is_empty(single_link_node_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Single_link_node at 0x7fea3855db38>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "single_link_node_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Double_link_list:\n",
    "    def __init__(self):\n",
    "        self.prev = None\n",
    "        self.head = None\n",
    "        self.next = None\n",
    "    def insert(self, node):\n",
    "        node.next = self"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
